{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10\n",
    "# 创建数组[1,2,3,4,5,6,7,8,9,10]\n",
    "list1 = []\n",
    "for i in range(1, n+1):\n",
    "    list1.append(i)\n",
    "# Python字符串可以用''或\"\"表示\n",
    "print('原始数组：', list1)\n",
    "position = 4\n",
    "value = \"x\"\n",
    "# 数据往后移动一个位置\n",
    "list1.append(list1[n-1])\n",
    "# -1是表示，i每一次减一，可以添任意整数，不填默认是1，\n",
    "for i in range(n, position-1, -1):\n",
    "    list1[i] = list1[i-1]\n",
    "list1[position-1] = value\n",
    "# 格式化输出，%s表示字符串\n",
    "print(\"插入%s后的新数组：\" % value, list1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 与内置函数比较"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 1000\n",
    "# 用函数创建数组\n",
    "list1 = list(range(1, n+1))\n",
    "position = 4\n",
    "value = \"x\"\n",
    "# 记录开始时间\n",
    "start = time.clock()\n",
    "list1.append(list1[n-1])\n",
    "for i in range(n, position-1, -1):\n",
    "    list1[i] = list1[i-1]\n",
    "list1[position-1] = value\n",
    "print(\"方法1运算时间：\", (time.clock() - start))\n",
    "# 使用Python内置方法\n",
    "start = time.clock()\n",
    "position = 7\n",
    "value = \"y\"\n",
    "list1.insert(position-1, value)\n",
    "print(\"方法2运算时间：\", (time.clock() - start))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 数组常见操作"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建数组\n",
    "list1 = ['数组', 1997, 17.5, [{\"a\":1},2,3]] # 混合不同类型\n",
    "list2 = [1]*4 # [1,1,1,1]\n",
    "# 引索从0开始\n",
    "list1[1]   # 1997\n",
    "list1[-1]  # -1是倒数第一个，[{\"a\":1},2,3]\n",
    "list1[1:3]  # 切片队列形成新的队列，[1997, 17.5]\n",
    "# 内置方法\n",
    "len(list2)          # 求列表长度, 4\n",
    "list2.count(1)      # 求列表中某个值的个数, 4\n",
    "list1.pop(2)        # 删除并返回index处的元素，默认为删除并返回最后一个元素\n",
    "list1.remove(1997)  # 删除列表中的value值，只删除第一次出现的value的值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战1:海盗船生存大考验"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Josephus_array(N,M,K):\n",
    "    \"\"\"\n",
    "    N:总人数\n",
    "    M:报数第Ｍ个出圈\n",
    "    K:圈内剩Ｋ个人结束\n",
    "    \"\"\"\n",
    "    result = []        # 保存结果，出圈位置编号\n",
    "    # 第一步验证输入参数是否正确\n",
    "    if type(K) == type(M) == type(N) == int:  # 是否为整数\n",
    "        # 确保为正整数，而且K小于N，否则直接输出结果为[]\n",
    "        if 0 < K < N and M > 0:\n",
    "            # 初始化程序\n",
    "            index = 0          # 下标\n",
    "            number = 0         # 报数计数\n",
    "            inside_count = N   # 圈内人数\n",
    "            circle = [1]*N     # 初始化数组，在圈内状态为1\n",
    "            \n",
    "            # 是否满足结束条件\n",
    "            while (inside_count > K):\n",
    "                number += circle[index]\n",
    "                if number == M:\n",
    "                    \"\"\"\n",
    "                    出圈步骤：\n",
    "                    1.记录这个人位置\n",
    "                    2.更改这个人的状态，变成出圈状态，1->0\n",
    "                    3.统计圈内人总数，也就是总人数减一\n",
    "                    4.报数归零\n",
    "                    \"\"\"\n",
    "                    result.append(index+1) # 数组下标默认是0开始\n",
    "                    circle[index] = 0\n",
    "                    inside_count -= 1\n",
    "                    number = 0\n",
    "                # 取模运算，使得index在0~count-1之间一直循环，达到循环数组\n",
    "                index = (index + 1) % N\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(Josephus_array(6,5,2))\n",
    "print(Josephus_array(100,6,\"213\"))\n",
    "print(Josephus_array(64,11,32))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import randint, choice\n",
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def game(N):\n",
    "    \"\"\"\n",
    "    N:游戏数字个数N,而且Ｎ必须是大于0的偶数\n",
    "    \"\"\"\n",
    "    # 第一步验证输入参数是否正确\n",
    "    if type(N) == int and N > 0 and N % 2 == 0:\n",
    "        # 初始化游戏，生成随机数列\n",
    "        choose_list = []\n",
    "        odd_sum = 0\n",
    "        even_sum = 0\n",
    "        # 记录比赛结果\n",
    "        computer_choose_sum = 0\n",
    "        player_choose_sum = 0\n",
    "        has_choose_index_list = [] #记录已经挑选的数字位置\n",
    "        for i in range(0, N):\n",
    "            number = randint(1,100)     # 范围1-99生成随机数\n",
    "            choose_list.append(number)  # 加入到数列里面\n",
    "            if i % 2 == 0:\n",
    "                even_sum += number      # 求偶数数列和\n",
    "            else:\n",
    "                odd_sum += number       # 求奇数数列和\n",
    "        # 输出初始化的数列，比赛开始\n",
    "        print(choose_list)\n",
    "        # 现在你就是计算机，所以计算机先选数字\n",
    "        # 先判断选择奇数例还是偶数列\n",
    "        if odd_sum > even_sum:\n",
    "            # 选择奇数列\n",
    "            choose_flag = 'odd'\n",
    "            # 在奇数位置中随机选择一个\n",
    "            choose_index = choice([i for i in range(1, N, 2)])\n",
    "        else:\n",
    "            # 选择偶数列\n",
    "            choose_flag = 'even'\n",
    "            # 在偶数位置中随机选择一个\n",
    "            choose_index = choice([i for i in range(0, N, 2)])\n",
    "        # 记录挑选的位置\n",
    "        has_choose_index_list.append(choose_index)\n",
    "        # 统计你的数字和\n",
    "        computer_choose_sum += choose_list[choose_index]\n",
    "        # 输出你选择的结果\n",
    "        print(\"计算机选择位置{}({}), 暂时总和{}\".format(\n",
    "            choose_index, choose_list[choose_index], computer_choose_sum))\n",
    "        while(True):\n",
    "            # 输出对手可以选择的数字\n",
    "            left_index = right_index = choose_index\n",
    "            step = 1\n",
    "            # 下标应该是所选数字下标左右两侧，若已经被选过了，继续往左(右)找下一个\n",
    "            while left_index in has_choose_index_list:\n",
    "                left_index = (choose_index - step) % N\n",
    "                step += 1\n",
    "            step = 1\n",
    "            while right_index in has_choose_index_list:\n",
    "                right_index = (choose_index + step) % N\n",
    "                step += 1\n",
    "            print(\"您可以选择的位置{left_i}({left_v})或{right_i}({right_v})\".format(\n",
    "                left_i=left_index,\n",
    "                right_i=right_index,\n",
    "                left_v=choose_list[left_index],\n",
    "                right_v=choose_list[right_index]))\n",
    "            input_pass = False\n",
    "            while not input_pass:\n",
    "                player_choose_index = input(\"请输入您选择的位置:\")\n",
    "                try:\n",
    "                    # 检查输入的合法性\n",
    "                    player_choose_index = int(player_choose_index)\n",
    "                    if player_choose_index == left_index or player_choose_index == right_index:\n",
    "                        # 输入正确，才能跳出循环，到下一步\n",
    "                        input_pass = True\n",
    "                    else:\n",
    "                        print(\"输入不合法,请输入{}或{}\".format(left_index, right_index))\n",
    "                except:\n",
    "                    # 若出错，继续循环等待下一个输入\n",
    "                    print(\"输入不合法,请输入{}或{}\".format(left_index, right_index))\n",
    "            # 记录挑选的位置\n",
    "            has_choose_index_list.append(player_choose_index)\n",
    "            # 统计对手的数字和\n",
    "            player_choose_sum += choose_list[player_choose_index]\n",
    "            print(\"您选择置{}({}), 暂时总和{}\".format(\n",
    "                player_choose_index, choose_list[player_choose_index], player_choose_sum))\n",
    "            \n",
    "            # 若挑选数字总数等于N,游戏结束\n",
    "            if len(has_choose_index_list) == N:\n",
    "                break\n",
    "            # 游戏继续,轮到你来选择\n",
    "            left_index = right_index = player_choose_index\n",
    "            step = 1\n",
    "            while left_index in has_choose_index_list:\n",
    "                left_index = (player_choose_index - step) % N\n",
    "                step += 1\n",
    "            step = 1\n",
    "            while right_index in has_choose_index_list:\n",
    "                right_index = (player_choose_index + step) % N\n",
    "                step += 1\n",
    "            # 继续执行计算机的游戏策略\n",
    "            if choose_flag == 'odd':\n",
    "                # 选择奇数列\n",
    "                if left_index % 2 == 1:\n",
    "                    choose_index = left_index\n",
    "                else:\n",
    "                    choose_index = right_index\n",
    "            else:\n",
    "                # 选择偶数列\n",
    "                if left_index % 2 == 1:\n",
    "                    choose_index = right_index\n",
    "                else:\n",
    "                    choose_index = left_index\n",
    "            # 记录挑选的位置\n",
    "            has_choose_index_list.append(choose_index)\n",
    "            computer_choose_sum += choose_list[choose_index]\n",
    "            # 输出你选择的结果\n",
    "            print(\"计算机选择位置{}({}), 暂时总和{}\".format(\n",
    "                choose_index, choose_list[choose_index], computer_choose_sum))\n",
    "        # 游戏结束,输出比赛结果\n",
    "        print(\"--------------比赛结束-------------------\")\n",
    "        print(\"计算机总分:%d, 您的总分:%d\" % (computer_choose_sum, player_choose_sum))\n",
    "        if computer_choose_sum == player_choose_sum:\n",
    "            print(\"平局\")\n",
    "        elif computer_choose_sum > player_choose_sum:\n",
    "            print(\"计算机赢了\")\n",
    "        else:\n",
    "            # 对手应该永远也看不到这个\n",
    "            print(\"恭喜您赢得比赛\")      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "game(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Python负数取模运算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# -1 % 5\n",
    "print(\"C 或 JAVA\", -1 - (5*math.trunc(-1/5)))\n",
    "print(\"Python\", -1 - (5*math.floor(-1/5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 链表\n",
    "### 定义数据结点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建数据结点对象\n",
    "class Node(object):\n",
    "    # 初始化结点信息\n",
    "    def __init__(self, data, pnext = None):\n",
    "        '''\n",
    "        data:节点保存的数据\n",
    "        next:指针\n",
    "        '''\n",
    "        self.data = data\n",
    "        self.next = pnext\n",
    "    #用于定义Node的字符输出\n",
    "    def __repr__(self):\n",
    "        '''\n",
    "        定义对象在屏幕输出时候的信息\n",
    "        '''\n",
    "        return str(self.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建单向链表对象\n",
    "class Chain(object):\n",
    "    # __xx__是Python对象魔法函数\n",
    "    # 初始化链表\n",
    "    def __init__(self):\n",
    "        # 链表头head,链表长度length\n",
    "        self.head = None\n",
    "        self.length = 0\n",
    "    def __repr__(self):\n",
    "        if (self.length == 0):\n",
    "            print(\"这是一个空链表\")\n",
    "            return\n",
    "        node = self.head\n",
    "        # 把链表信息记录为一个字符串\n",
    "        node_list = []\n",
    "        while node:\n",
    "            node_list.append(str(node.data))\n",
    "            node = node.next\n",
    "        return \" \".join(node_list)\n",
    "    \n",
    "    def __len__(self):\n",
    "        # 让 len() 函数工作，类必须提供一个特殊方法__len__()，它返回元素的个数\n",
    "        return self.length  \n",
    "           \n",
    "    # 增加一个节点（在链尾部添加）\n",
    "    def append(self, dataOrNode):\n",
    "        item = None\n",
    "        if isinstance(dataOrNode, Node):\n",
    "            item = dataOrNode\n",
    "        else:\n",
    "            item = Node(dataOrNode)\n",
    "        \n",
    "        # 如果是第一个结点\n",
    "        if not self.head:\n",
    "            # 把这个结点作为head\n",
    "            self.head = item\n",
    "            self.length += 1\n",
    "        else:\n",
    "            # 寻找链表尾部结点\n",
    "            node = self.head\n",
    "            while node.next:\n",
    "                node = node.next\n",
    "            node.next = item\n",
    "            self.length += 1\n",
    "    \n",
    "    # 在索引值为index的结点后插入结点key\n",
    "    def insert_node(self, key, index):\n",
    "        if index == 0:\n",
    "            # 头部插入新结点\n",
    "            node = Node(key)\n",
    "            node.next = self.head\n",
    "            self.head = node\n",
    "        else:\n",
    "            pnext= self.head\n",
    "            j = 1\n",
    "            while pnext and j < index:\n",
    "                pnext = pnext.next\n",
    "                j += 1\n",
    "            if(pnext == None or j > index): #若出错返回空\n",
    "                print('插入结点出错')\n",
    "                return\n",
    "            node = Node(key)\n",
    "            node.next = pnext.next\n",
    "            pnext.next = node\n",
    "        \n",
    "        self.length += 1\n",
    "        print('插入结点后的链表：')\n",
    "        print(self)\n",
    "    \n",
    "    # 删除一个节点： delete()\n",
    "    def delete(self, index):\n",
    "        if (self.length == 0):\n",
    "            print(\"这是一个空链表\")\n",
    "            return\n",
    "        if index < 0 or index >= self.length:\n",
    "            print('下标出错')\n",
    "            return\n",
    "\n",
    "        # 删除第一个节点的情况\n",
    "        if index == 0:\n",
    "            self.head = self.head.next\n",
    "            self.length -= 1\n",
    "        else:\n",
    "            '''\n",
    "            prev为保存前一个结点\n",
    "            node为保存当前结点\n",
    "            '''\n",
    "            j = 0\n",
    "            node = self.head\n",
    "            prev = self.head\n",
    "            while node.next and j < index:\n",
    "                prev = node\n",
    "                node = node.next\n",
    "                j += 1\n",
    "\n",
    "            if j == index:\n",
    "                prev.next = node.next\n",
    "                self.length -= 1\n",
    "        print('删除结点后的链表：')\n",
    "        print(self)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "chain = Chain()\n",
    "for data in [20,31,40]:\n",
    "    chain.append(data)\n",
    "print(\"初始链表：\", chain)\n",
    "chain.insert_node(26, 1)\n",
    "chain.insert_node(100, 0)\n",
    "print(\"链表长度：\", len(chain))\n",
    "chain.delete(4)\n",
    "chain.delete(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战1：国王的继承人"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 我们继续使用上面创建的Node对象\n",
    "def create_chain(n):\n",
    "    # 创建循环链表\n",
    "    if n <= 0:\n",
    "        return False\n",
    "    if n == 1:\n",
    "        return Node(1)\n",
    "    else:\n",
    "        # 多于一个做成循环链表\n",
    "        head = Node(1)\n",
    "        pnext = head\n",
    "        # 创建数据结点\n",
    "        for i in range(2,n + 1):\n",
    "            pnext.next = Node(i)\n",
    "            pnext = pnext.next\n",
    "        # 把尾部结点指针指向头部结点，形成循环链表\n",
    "        pnext.next = head\n",
    "        return head\n",
    "\n",
    "def show_chain(head):\n",
    "    # 输出链表\n",
    "    pnext = head\n",
    "    node_list = []\n",
    "    while True:\n",
    "        node_list.append(str(pnext.data))\n",
    "        pnext = pnext.next\n",
    "        if pnext == None or pnext == head:\n",
    "            break\n",
    "    return \" \".join(node_list)\n",
    "\n",
    "def josephus_chain(n,m):\n",
    "    if m == 1:\n",
    "        print('王子人选',n)\n",
    "        return\n",
    "    # 创建循环链表\n",
    "    head = create_chain(n)\n",
    "    if not head:\n",
    "        print(\"输入有误\")\n",
    "        return\n",
    "    # 显示链表\n",
    "    print(\"初始链表：\", show_chain(head))\n",
    "    pnext = head\n",
    "    # 程序运行到剩最后一个结点时候结束\n",
    "    while pnext.next != pnext:\n",
    "        for i in range(0, m-1):\n",
    "            prev = pnext\n",
    "            pnext = pnext.next\n",
    "        print('淘汰的人',pnext.data)\n",
    "        # 绕开出圈的结点\n",
    "        prev.next = pnext.next\n",
    "        pnext = prev.next\n",
    "    print('王子人选', pnext.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "josephus_chain(6, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 数组实现队列\n",
    "class Queue(object):\n",
    "    def __init__(self):\n",
    "        #初始化列表\n",
    "        self.items = []    \n",
    "    def __len__(self):\n",
    "        return len(self.items)\n",
    "    def is_empty(self):\n",
    "        return len(self.items) == 0    \n",
    "    def add(self, value):\n",
    "        # 数据插入队列\n",
    "        return self.items.append(value)\n",
    "    # 出队\n",
    "    def delete(self):\n",
    "        if self.is_empty():\n",
    "            raise Exception(\"队列为空\")\n",
    "        # pop是删除列表元素，默认是删除最后有一个，添加下标后，可以删除指定下标数据\n",
    "        return self.items.pop(0)    \n",
    "    # 输出队列数据\n",
    "    def show_queue(self):\n",
    "        print(self.items)\n",
    "\n",
    "# 继承列表属性和方法来构建队列\n",
    "class Queue2(list):\n",
    "    # 只需要改写出队规则就好\n",
    "    def pop(self):\n",
    "        if len(self) == 0:\n",
    "            raise Exception(\"队列为空\")\n",
    "        # 继承后覆盖pop方法\n",
    "        super(Queue2, self).pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "q = Queue()\n",
    "print(\"初始化q队列：\", q.items)\n",
    "print(\"队列是否为空：\", \"是\" if q.is_empty() else \"否\")\n",
    "for i in range(1, 4):\n",
    "    # 插入数据\n",
    "    q.add(i)\n",
    "q.show_queue()\n",
    "print(\"队列是否为空：\", \"是\" if q.is_empty() else \"否\")\n",
    "print(\"删掉一个数据\")\n",
    "q.delete()\n",
    "q.show_queue()\n",
    "print(\"插入一个数据5,然后删掉一个数据\")\n",
    "q.add(5)\n",
    "q.delete()\n",
    "q.show_queue()\n",
    "q.delete()\n",
    "q.delete()\n",
    "q.delete()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "q = Queue2()\n",
    "for i in range(1, 4):\n",
    "    # 插入数据\n",
    "    q.append(i)\n",
    "print(q)\n",
    "q.pop()\n",
    "print(q)\n",
    "q.pop()\n",
    "q.pop()\n",
    "q.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战1：维修警报器"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 我们使用上面创建的队列类Queue2\n",
    "q = Queue2()\n",
    "# 标准产品的参数\n",
    "M = 500   # 平均质量\n",
    "C = 10    # 标准差\n",
    "point_count = 7 # 测量7个点平均数 \n",
    "# 模拟生成数据，用randint产生随机数，所以程序运行结果，不是每一次都一样，可以适当调整随机数参数生产出合适的数据\n",
    "input_data = [randint(M-1*C-1, M+5*C) for i in range(30)]\n",
    "print(\"生产数据：\",input_data)\n",
    "for data in input_data:\n",
    "    q.append(data)\n",
    "    # 队列长度是否达到要求 \n",
    "    if len(q) == point_count:\n",
    "        # abs求绝对值\n",
    "        result = abs(sum(q) / point_count - M)\n",
    "        # 平均值超过标准差3倍时候\n",
    "        if result > 3*C:\n",
    "            print(\"机器出错！\", \"错误数据为：\", q)\n",
    "            print(\"平均值为：\", result)\n",
    "            # 停止机器，也就是中断循环\n",
    "            break\n",
    "        # 队列已满，因此要把队头数据清除\n",
    "        q.pop()\n",
    "else:\n",
    "    # 程序在循环中若没有中断，就输出这句话\n",
    "    print('数据全部合格')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Stack(object):\n",
    "    # 模拟栈的功能\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    def isEmpty(self):\n",
    "        # 判断栈是否为空\n",
    "        return len(self.items)==0\n",
    "    def size(self):\n",
    "        # 返回栈的元素个数\n",
    "        return len(self.items) \n",
    "    def push(self, item):\n",
    "        # 添加元素\n",
    "        self.items.append(item)\n",
    "    def pop(self):\n",
    "        # 删除元素\n",
    "        return self.items.pop() \n",
    "    def show(self):\n",
    "        # 输出栈里面的所有元素,先进后出\n",
    "        print(\"输出栈元素：\",self.items[::-1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "stack = Stack()\n",
    "print(\"新建栈，栈必定为空\", stack.isEmpty())\n",
    "for i in range(3):\n",
    "    stack.push(i)\n",
    "print(\"入栈元素0,1,2\")\n",
    "stack.show()\n",
    "print(\"出栈\")\n",
    "stack.pop()\n",
    "stack.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 用deque实现队列\n",
    "import collections\n",
    "queue = collections.deque()\n",
    "for i in range(6):\n",
    "    queue.append(i)\n",
    "print('初始化队列', queue)\n",
    "# 双向队列添加元素默认是在右边插入\n",
    "queue.append(6)\n",
    "print('添加元素6', queue)\n",
    "# 双向队列pop删除元素默认也是右边删除，所以要用popleft说明在左边删除\n",
    "# 右进左出，这样就构成一个队列结构\n",
    "queue.popleft()\n",
    "print('删除一个元素', queue)\n",
    "# 用deque实现栈\n",
    "print('---------------------------------')\n",
    "stack = collections.deque()\n",
    "for i in range(6):\n",
    "    # 添加元素也是可以从左边插入\n",
    "    stack.appendleft(i*2)\n",
    "print('初始化栈', stack)\n",
    "stack.appendleft(12)\n",
    "print('添加元素12', stack)\n",
    "# 删除元素和插入元素都在左边构成了栈结构\n",
    "stack.popleft()\n",
    "stack.popleft()\n",
    "print('删除两个元素', stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def change_10_to_2(data):\n",
    "    input_data = data\n",
    "    stack = collections.deque()    # 创建栈保存每次余数\n",
    "    quotient = data \n",
    "    while quotient > 0:  # 直到商为0才结束\n",
    "        quotient =  data // 2 # 除2商\n",
    "        remainder = data % 2  # 除2余数\n",
    "        stack.appendleft(str(remainder)) # 在栈顶插入数据\n",
    "        data = quotient\n",
    "    print(input_data, \"二进制编码:\", \"\".join(stack))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "change_10_to_2(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战2：机器人帮你检查作业"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_correct(formula):  \n",
    "    \"\"\"\n",
    "    判断数学算式中括号是否正确\n",
    "    formula 数学算式字符串\n",
    "    结果：\n",
    "    True无括号或所有括号全部匹配\n",
    "    False 存在括号不匹配\n",
    "    指出错误的位置\n",
    "    \"\"\"\n",
    "    stack = []    # 使用列表list模拟栈，保存括号\n",
    "    formula = formula.replace(\" \", \"\") # 去除多余空格\n",
    "    for index, char in enumerate(formula, 1):\n",
    "        # enumerate是枚举数据时候，添加下标\n",
    "        if  char == \"(\":   # 左边号,入栈括号的位置\n",
    "            stack.append(index)\n",
    "        elif char == \")\":  # 右括号，查看栈数据是否匹配\n",
    "            if len(stack) > 0:\n",
    "                # 如果栈里面有左括号，弹出栈顶元素\n",
    "                stack.pop()\n",
    "            else:\n",
    "                # 若为空，缺少左括号匹配\n",
    "                return False, index\n",
    "    if len(stack) > 0:\n",
    "        # 如果还有左括号，说明漏掉了右括号，返回匹配错误\n",
    "        # 如果有多个数据，只是输出栈顶的数据\n",
    "        return False, stack.pop() \n",
    "    return True, 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "input_data = [\n",
    "    \"(5+7) / (9-6) = 4\",\n",
    "    \"10+9) * 2+3 = 41\",\n",
    "    \"15 / (9-4 = 3 \",\n",
    "    \"15+9) / ((9-4*5 = 3\"\n",
    "]\n",
    "for data in input_data:\n",
    "    is_pass, index = is_correct(data)\n",
    "    print(data, \"正确\" if is_pass else \"位置%s出错\" % index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 哈希表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建数据类\n",
    "class DataItem(object):\n",
    "    # 初始化数据\n",
    "    def __init__(self, key, value):\n",
    "        '''\n",
    "        key:关键值\n",
    "        value:数据值\n",
    "        '''\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "    #用于定义输出\n",
    "    def __repr__(self):\n",
    "        return \"({}:{})\".format(self.key, self.value)\n",
    "# 创建哈希表类\n",
    "class MyHashTable(object):\n",
    "    def __init__(self,size):\n",
    "        self.no_use = None # 表示DataItem未被使用过\n",
    "        self.size = size # 哈希表大小\n",
    "        self.table = [self.no_use]*size  # 存储数据的表\n",
    "    #用于定义输出\n",
    "    def __repr__(self):\n",
    "        output_data = []\n",
    "        for index, data in enumerate(self.table):\n",
    "            if data:\n",
    "                output_data.append(\"{}:{}\".format(index, str(data)))\n",
    "            else:\n",
    "                output_data.append(\"{}:{}\".format(index, None))\n",
    "        return \",\".join(output_data)\n",
    "    # 散列函数\n",
    "    def hash(self, key):\n",
    "        return key % self.size\n",
    "    # 插入数据\n",
    "    def add(self, key, value):\n",
    "        item = DataItem(key, value)\n",
    "        hash_index = self.hash(key) #根据散列函数计算出地址索引\n",
    "        step = 0\n",
    "        while( self.table[hash_index] != self.no_use and step < self.size):\n",
    "            # 若发生哈希冲突，看下一个索引是否可用\n",
    "            hash_index = (hash_index + 1) % self.size\n",
    "            step += 1\n",
    "        \n",
    "        if step == self.size:\n",
    "            # 遍历表也没有找到空余空间\n",
    "            return False  # 返回False 表示空间已经满足了，没有执行插入操作\n",
    "        else:\n",
    "            # 成功插入数据\n",
    "            self.table[hash_index] = item\n",
    "            return True\n",
    "    # 寻找数据\n",
    "    def search(self, key):\n",
    "        hash_index = self.hash(key) \n",
    "        step = 0\n",
    "        while( self.table[hash_index] != self.no_use and step < self.size):\n",
    "            if self.table[hash_index].key == key:\n",
    "                return self.table[hash_index]  # 找到数据，马上返回\n",
    "            hash_index = (hash_index + 1) % self.size\n",
    "            step += 1\n",
    "        return\n",
    "    # 删除数据             \n",
    "    def delete(self, key):\n",
    "        hash_index = self.hash(key) \n",
    "        step = 0\n",
    "        while( self.table[hash_index] != self.no_use and step < self.size):\n",
    "            if self.table[hash_index].key == key:\n",
    "                tmp_item =  self.table[hash_index]\n",
    "                self.table[hash_index] = self.no_use\n",
    "                return tmp_item   # 返回删除的元素\n",
    "            hash_index = (hash_index + 1) % self.size\n",
    "            step += 1\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建一个大小为20的哈希表\n",
    "table1 = MyHashTable(20)\n",
    "# 输入例子数据\n",
    "datas = [(1,20),(2,70),(42,80),(7,25),(12,44),(14,32),(17,11),(37,78),(13,98),(25, 61)]\n",
    "for data in datas:\n",
    "    #添加数据\n",
    "    table1.add(data[0], data[1])\n",
    "print(\"初始化的哈希表\", table1)\n",
    "print(\"寻找数据\", table1.search(42))\n",
    "print(\"删除数据\", table1.delete(37))\n",
    "print(\"删除数据后的哈希表\", table1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 继续使用上面的数据table1\n",
    "table1 = MyHashTable(20)\n",
    "for i in range(20):\n",
    "    table1.add(i, i)\n",
    "print(table1.search(50))\n",
    "print(table1.search(12))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 常用字典常量和操作\n",
    "D = {}\n",
    "D = {'spam':2, 'tol':{'ham':1}}                   # 嵌套字典\n",
    "D = dict.fromkeys(['s', 'd'], 8)                  # {'s': 8, 'd': 8}\n",
    "D = dict(name = 'tom', age = 12)                  # {'age': 12, 'name': 'tom'}\n",
    "D = dict([('name', 'tom'), ('age', 12)])          # {'age': 12, 'name': 'tom'}\n",
    "D = dict(zip(['name', 'age'], ['tom', 12]))       # {'age': 12, 'name': 'tom'}\n",
    "D.keys(); D.values(); D.items()                   # 字典键、值以及键值对\n",
    "D.get(key, default)                               # get函数\n",
    "D.update(D_other)                                 # 合并字典，如果存在相同的键值，D_other的数据会覆盖掉D的数据\n",
    "D.pop(key, [D])                                   # 删除字典中键值为key的项，返回键值为key的值，如果不存在，返回默认值D，否则异常\n",
    "D.popitem()                                       # pop字典中随机的一项（一个键值对）\n",
    "del D                                             # 删除字典\n",
    "del D['key']                                      # 删除字典的某一项"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "D = {'a':1, 'b':2, 'c':3}\n",
    "print('字典键列表：',D.keys())\n",
    "print('字典值列表：',D.values())\n",
    "print('字典键值列表：',D.items())\n",
    "print('通过键获取字典值', D.get('a', 0))\n",
    "print('通过键获取字典值，若没有，则返回预设值0：', D.get('d', 0))\n",
    "add_dict = {'d':5, 'a':6, 'e':10}\n",
    "D.update(add_dict) # '合并字典，如果存在相同的键值，add_dict的数据会覆盖掉D的数据\n",
    "print('合并后的字典', D)\n",
    "print('删除字典中键值为a的项', D.pop('a'))\n",
    "print('pop字典中随机的一项', D.popitem())\n",
    "del D['b'] # 删除字典某一项\n",
    "del D # 删除字典"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import Counter  # 再次使用集合库，Counter可以统计字符串出现次数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def find_DNA_sequences(DNA_sequence, n):\n",
    "    keys = [] # 把所有基因组合记录下来\n",
    "    for i in range(len(DNA_sequence) - n+1):\n",
    "        # 理解为一个滑动窗口，如AGTTCGA 用一个4字符串大小窗口观察可以得到['AGTT', 'GTTC', 'TTCG', 'TCGA']\n",
    "        keys.append(DNA_sequence[i: i + n])\n",
    "    return Counter(keys) #统计列表里面的基因组合的数量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sequences = \"CCCAGTTAACGTTAAACCCCCCGTAAAGGGC\"\n",
    "res = find_DNA_sequences(sequences, 4)\n",
    "print('原始结果是一个无序字典')\n",
    "for key, value in res.items():\n",
    "    if value > 1:  # 按要求只显示有重复出现的基因序列\n",
    "        print(key, value)\n",
    "# 通过sorted函数让结果按照基因出现的次数从大到小排序\n",
    "res = sorted(res.items(), key=lambda x: x[1], reverse=True) \n",
    "print('排序后的结果成功一个有序列表')\n",
    "for item in res:\n",
    "    if item[1] > 1:\n",
    "        print(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def hash_code(sequence):\n",
    "    code_map = {\n",
    "        'A': '00',\n",
    "        'C': '01',\n",
    "        'G': '10',\n",
    "        'T': '11'\n",
    "    }\n",
    "    code = []\n",
    "    for key in sequence:\n",
    "        if key not in code_map.keys():\n",
    "            return None\n",
    "        code.append(code_map[key])\n",
    "    code = int(\"\".join(code), 2)  # 二进制转换十进制\n",
    "    return code    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class User:\n",
    "    def __init__(self, name, gender, work):\n",
    "        self.name = name\n",
    "        self.gender = gender\n",
    "        self.work = work\n",
    "        \n",
    "    def __hash__(self):\n",
    "        # 定义散列函数\n",
    "        return hash((self.name, self.gender, self.work))\n",
    "    \n",
    "    def __eq__(self, other):\n",
    "        # 三个属性一样，就认为是同一个人\n",
    "        return self.name == other.name and self.gender == other.gender and self.work == other.work\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "u1 = User('小明', '男', '公司A')\n",
    "u2 = User('小明', '男', '公司B')\n",
    "u3 = User('小明', '男', '公司B')\n",
    "print(hash(u1))\n",
    "print(hash(u2))\n",
    "print(hash(u3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(u3 == u2)\n",
    "print(u3 == u1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建结点对象\n",
    "class TreeNode(object):\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        if left is not None and not isinstance(left, TreeNode):\n",
    "            raise ValueError('左孩子结点必须是结点类')\n",
    "        if right is not None and not isinstance(right, TreeNode):\n",
    "            raise ValueError('左孩子结点必须是结点类')\n",
    "        self.value = value  # 结点值\n",
    "        self.left = left    # 左孩子结点\n",
    "        self.right = right  # 右孩子结点\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'TreeNode({})'.format(self.value)\n",
    "    \n",
    "    def insert_left(self,value):\n",
    "        # 在左边插入新的结点\n",
    "        if self.left == None:\n",
    "            self.left = TreeNode(value)\n",
    "        else:\n",
    "            # 若结点存在，把原来结点放到新结点的左孩子结点\n",
    "            tmp = TreeNode(value)\n",
    "            tmp.left = self.left\n",
    "            self.left = tmp\n",
    "            \n",
    "    def insert_right(self,value):\n",
    "        # 在右边插入新的结点\n",
    "        if self.right == None:\n",
    "            self.right = TreeNode(value)\n",
    "        else:\n",
    "            # 若结点存在，把原来结点放到新结点的右孩子结点\n",
    "            tmp = TreeNode(value)\n",
    "            tmp.right = self.right\n",
    "            self.right = tmp\n",
    "            \n",
    "    def pre_order_traversal(self):\n",
    "        # 先序遍历：根-左-右\n",
    "        result = [self.value]   # 先访问根结点\n",
    "        if self.left:\n",
    "            # 再访问左边子树，在子树里面递归使用先序遍历里面的结点\n",
    "            result += self.left.pre_order_traversal()\n",
    "        if self.right:\n",
    "            # 最后访问右边子树\n",
    "            result += self.right.pre_order_traversal()\n",
    "        return result\n",
    "    \n",
    "    def in_order_traversal(self):\n",
    "        # 中序遍历：左-根-右\n",
    "        result = []\n",
    "        if self.left:\n",
    "            # 遍历左边子树\n",
    "            result += self.left.in_order_traversal()\n",
    "        # 接着访问根结点\n",
    "        result.append(self.value)\n",
    "        if self.right:\n",
    "            # 遍历右边子树\n",
    "            result += self.right.in_order_traversal()\n",
    "        return result\n",
    "    \n",
    "    def post_order_traversal(self):\n",
    "        # 后序遍历：左-右-根\n",
    "        result = []\n",
    "        if self.left:\n",
    "            result += self.left.post_order_traversal()\n",
    "        if self.right:\n",
    "            result += self.right.post_order_traversal()\n",
    "        result.append(self.value)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建二叉树例子\n",
    "binary_tree = TreeNode('A')\n",
    "binary_tree.insert_left('B')\n",
    "binary_tree.insert_right('C')\n",
    "binary_tree.left.insert_left('D')\n",
    "binary_tree.left.insert_right('E')\n",
    "binary_tree.right.insert_left('F')\n",
    "binary_tree.right.insert_right('G')\n",
    "# 根据三种遍历方式，访问二叉树的数据\n",
    "res = binary_tree.pre_order_traversal()\n",
    "print(\"先序遍历\", \"->\".join(res))\n",
    "res = binary_tree.in_order_traversal()\n",
    "print(\"中序遍历\", \"->\".join(res))\n",
    "res = binary_tree.post_order_traversal()\n",
    "print(\"后序遍历\", \"->\".join(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def if_perfect(tree):\n",
    "    # 根据完美二叉树定义，它的叶子数量=2^(树的深度-1)\n",
    "    max_depth = 0  # 树最大的深度\n",
    "    leaf_count = 0       # 叶子数量\n",
    "    size = 0             # 结点数量\n",
    "    current_nodes = [tree]\n",
    "    \n",
    "    while len(current_nodes) > 0:\n",
    "        max_depth += 1\n",
    "        next_nodes = []\n",
    "        \n",
    "        for node in current_nodes:\n",
    "            size += 1\n",
    "            if node.left is None and node.right is None:\n",
    "                leaf_count += 1  # 根据定义，没有孩子结点就是叶子结点\n",
    "            if node.left is not None:\n",
    "                next_nodes.append(node.left)\n",
    "            if node.right is not None:\n",
    "                next_nodes.append(node.right)\n",
    "        current_nodes = next_nodes\n",
    "                \n",
    "    print(\"叶子的深度{},叶子数量{},因此它{}完美二叉树\".format(\n",
    "        max_depth,leaf_count,\n",
    "        \"是\" if leaf_count == 2 ** (max_depth-1) else \"不是\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "if_perfect(binary_tree)\n",
    "binary_tree.right.right.insert_right('H')\n",
    "if_perfect(binary_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二叉查找树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建二叉查找树结点对象\n",
    "class BinarySearchTreeNode(object):\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        if left is not None and not isinstance(left, TreeNode):\n",
    "            raise ValueError('左孩子结点必须是结点类')\n",
    "        if right is not None and not isinstance(right, TreeNode):\n",
    "            raise ValueError('左孩子结点必须是结点类')\n",
    "        self.value = value  # 结点值\n",
    "        self.left = left    # 左孩子结点\n",
    "        self.right = right  # 右孩子结点\n",
    "    def __repr__(self):\n",
    "        return 'TreeNode({})'.format(self.value)\n",
    "    def insert(self, value):\n",
    "        # 二叉查找树插入操作\n",
    "        if value <= self.value:\n",
    "            # 左子树所有值<=双亲结点\n",
    "            if self.left:\n",
    "                self.left = self.left.insert(value)\n",
    "            else:\n",
    "                self.left = BinarySearchTreeNode(value)\n",
    "        elif value > self.value:\n",
    "            # 双亲结点<右子树所有值\n",
    "            if self.right:\n",
    "                self.right = self.right.insert(value)\n",
    "            else:\n",
    "                self.right = BinarySearchTreeNode(value)\n",
    "        return self\n",
    "    def in_order_traversal(self):\n",
    "        result = []\n",
    "        if self.left:\n",
    "            result += self.left.in_order_traversal()\n",
    "        result.append(self.value)\n",
    "        if self.right:\n",
    "            result += self.right.in_order_traversal()\n",
    "        return result\n",
    "    def find_min(self):\n",
    "        # '查找二叉搜索树中最小值点\n",
    "        if self.left:\n",
    "            return self.left.find_min()\n",
    "        else:\n",
    "            return self\n",
    "    def find_max(self):\n",
    "        # 查找二叉查找树中最大值点\n",
    "        if self.right:\n",
    "            return self.right.find_max()\n",
    "        else:\n",
    "            return self\n",
    "    def del_node(self, value):\n",
    "        # 删除二叉搜索树中值为value的点\n",
    "        if self == None:\n",
    "            return \n",
    "        if value < self.value:\n",
    "            self.left = self.left.del_node(value)\n",
    "        elif value > self.value:\n",
    "            self.right = self.right.del_node(value)\n",
    "        # 当value=self.value时，分为三种情况：只有左子树;只有右子树;有左右子树或者即无左子树又无右子树\n",
    "        else:\n",
    "            if self.left and self.right:\n",
    "                # 既有左子树又有右子树，则需找到右子树中最小值节点\n",
    "                tmp = self.right.find_min()\n",
    "                self.value = tmp.value\n",
    "                # 再把右子树中最小值节点删除\n",
    "                self.right = self.right.del_node(tmp.value)\n",
    "            elif self.right == None and self.left == None:  # 左右子树都为空\n",
    "                self = None\n",
    "            elif self.right == None:   # 只有左子树\n",
    "                self = self.left\n",
    "            elif self.left == None:    # 只有右子树\n",
    "                self = self.right\n",
    "        return self"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tree  = BinarySearchTreeNode(20) # 创建根结点20\n",
    "for data in [11,27,5,18,14,19]:  # 插入数值，和上面例子一样\n",
    "    tree.insert(data)\n",
    "res = tree.in_order_traversal()\n",
    "print(\"中序遍历\",res)\n",
    "print(tree.find_max())\n",
    "print(tree.find_min())\n",
    "tree.del_node(19)  \n",
    "tree.del_node(18) # 删掉一个数，再查看是否有序\n",
    "tree.del_node(14) \n",
    "print(tree.in_order_traversal())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_tree(root):\n",
    "    \"\"\"\n",
    "    输入根结点: 使用上面定义的BinarySearchTreeNode\n",
    "    结果是: 多行字符串\n",
    "    \"\"\"\n",
    "    def get_tree_level(node):\n",
    "        # 返回树的层数\n",
    "        if not node:\n",
    "            return 0\n",
    "        return 1 + max(get_tree_level(node.left), get_tree_level(node.right))\n",
    "\n",
    "    rows = get_tree_level(root)\n",
    "    cols = 2 ** rows - 1  # 根据深度算出预留空间大小\n",
    "    res = [[\" \"]*cols for _ in range(rows)]\n",
    "    trunks = [[\" \"]*cols for _ in range(rows-1)]\n",
    "    def build_tree(node, level, pos, parent_index):\n",
    "        if not node:\n",
    "            return\n",
    "        left_padding = 2 ** (rows - level - 1) - 1  # 偏移量\n",
    "        spacing = 2 ** (rows - level) - 1           # 左右孩子结点偏移\n",
    "        index = left_padding + pos * (spacing + 1)  # 确定偏移位置下标\n",
    "\n",
    "        if parent_index:  # 根据双亲结点和孩子结点的下标，求出＂树枝＂的下标\n",
    "            if parent_index > index:\n",
    "                trunk_index = index + (parent_index - index) // 2\n",
    "                trunk_val = \"/\"\n",
    "            else:\n",
    "                trunk_index = parent_index + (index - parent_index) // 2\n",
    "                trunk_val = \"\\\\\"  # 第一个＂\\＂是Python关键字，表示转义特殊字符，第二个＂\\＂代表字符\\\n",
    "            trunks[level-1][trunk_index] = trunk_val\n",
    "        \n",
    "        res[level][index] = str(node.value)         # 填入对应结点的数值\n",
    "        build_tree(node.left, level + 1, pos << 1, index)  # 是否有下一个左结点\n",
    "        build_tree(node.right, level + 1, (pos << 1) + 1, index) # # 是否有下一个右结点，\n",
    "    \n",
    "    build_tree(root, 0, 0, None)\n",
    "    # 在屏幕中输出二叉树\n",
    "    for level in range(len(trunks)):\n",
    "        print(\"\".join(res[level]))  # 把列表数据变成字符串输出\n",
    "        print(\"\".join(trunks[level])) \n",
    "    print(\"\".join(res[-1]))\n",
    "\n",
    "def insert_data(data):\n",
    "    \"\"\"按题目要求的输入，然后创建二叉查找树\"\"\"\n",
    "    tree  = BinarySearchTreeNode(data[0]) # 创建根结点\n",
    "    for value in data[1:]:  # 插入数值\n",
    "        tree.insert(value)\n",
    "    return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tree = insert_data([12,4,9,20,14,15])\n",
    "res = tree.in_order_traversal()\n",
    "print(\"中序遍历\",res)\n",
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tree = insert_data([70,40,90,80,100,50,34])\n",
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 图\n",
    "### 邻接矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 根据图1-39,创建邻接矩阵\n",
    "E,D,H,I = range(4)\n",
    "adjacency_matrix =[\n",
    "    [0, 1, 1, 0],\n",
    "    [1, 0, 0, 1],\n",
    "    [1, 0, 0, 1],\n",
    "    [0, 1, 1, 0]]\n",
    "# 邻接矩阵可以直观判断两个顶点是否关联\n",
    "print(\"E和D关联\" if adjacency_matrix[E][D] else \"E和D不关联\" )\n",
    "print(\"E和I关联\" if adjacency_matrix[E][I] else \"E和I不关联\" )\n",
    "# 如果我们要把权重带上，可以在邻接矩阵上把1替换成权重，创建有权无向图邻接矩阵\n",
    "adjacency_matrix_2 =[\n",
    "    [0, 10, 4, 0],\n",
    "    [10, 0, 0, 6],\n",
    "    [4, 0, 0, 17],\n",
    "    [0, 6, 17, 0]]\n",
    "print(\"E-D:\", adjacency_matrix_2[E][D])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 邻接列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 根据图1-37,创建有权有向图的邻接列表\n",
    "adjacency_list = {\n",
    "  杨过:{郭靖:'伯伯', 小龙女:'姑姑', 陆无双:'喜欢', 程英:'喜欢'},\n",
    "  郭靖:{黄药师:'岳父'},\n",
    "  黄药师:{程英:'徒弟'},\n",
    "  程英:{杨过:'喜欢',陆无双:'表妹'},\n",
    "  陆无双:{杨过:'喜欢'},\n",
    "  李莫愁:{陆无双:'徒弟'},\n",
    "  小龙女:{李莫愁:'师姐'},\n",
    "}\n",
    "print(\"郭靖是杨过的%s\" % adjacency_list[杨过][郭靖])\n",
    "print(\"黄药师是郭靖的%s\" % adjacency_list[郭靖][黄药师])\n",
    "# 创建有无有向图的邻接列表\n",
    "graph = {'A': set(['B', 'C']),\n",
    "         'B': set(['A', 'D', 'E']),\n",
    "         'C': set(['A', 'F']),\n",
    "         'D': set(['B']),\n",
    "         'E': set(['B', 'F']),\n",
    "         'F': set(['C', 'E'])}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 图的遍历\n",
    "#### 深度优先搜索法（DFS）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A->B->D->E->F->C->G\n"
     ]
    }
   ],
   "source": [
    "# 创建有无有向图的邻接列表\n",
    "graph = {'A': ['B', 'C'],\n",
    "         'B': ['A', 'D', 'E'],\n",
    "         'C': ['A', 'F', 'G'],\n",
    "         'D': ['B'],\n",
    "         'E': ['B', 'F', 'G'],\n",
    "         'F': ['C', 'E'],\n",
    "         'G': ['C', 'E']}\n",
    "\n",
    "def graph_dfs(adjacency_list, start_point):\n",
    "    \"\"\"图的深度优先搜索法\"\"\"\n",
    "    visited = [start_point]      # 保存已经访问过的顶点\n",
    "    stack = [[start_point, 0]]   # 用栈数据结构来记录访问历史，\n",
    "    #result = [start_point]\n",
    "    while stack: # 当栈为空，说明全部顶点已经遍历完成\n",
    "        (current_point, next_point_index) = stack[-1]  # 获取当前访问的顶点\n",
    "        if (current_point not in adjacency_list) or (next_point_index >= len(adjacency_list[current_point])):\n",
    "            stack.pop() # 当前顶点没有新的可以访问关联顶点，那么就出栈\n",
    "            continue\n",
    "        next_point = adjacency_list[current_point][next_point_index]\n",
    "        stack[-1][1] += 1            # 记录当前访问的顶点的这个关联顶点已经被访问\n",
    "        if next_point in visited:    # 若已经访问了，继续找下一个\n",
    "            continue\n",
    "        visited.append(next_point)   # 若是新的顶点，那就添加到已访问顶点\n",
    "        stack.append([next_point, 0])# 新的顶点入栈　\n",
    "    return visited  # 返回访问顶点的结果\n",
    "#------------测试--------------------\n",
    "res = graph_dfs(graph, 'A')\n",
    "print(\"->\".join(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0->1->4->7->8->2->5->9->3->6\n"
     ]
    }
   ],
   "source": [
    "# 拓扑排序例子，5-9\n",
    "graph2 = {'0': ['1','2','3'],\n",
    "         '1': ['4'],\n",
    "         '2': ['5'],\n",
    "         '3': ['6'],\n",
    "         '4': ['7'],\n",
    "         '5': ['9'],\n",
    "         '6': ['7'],\n",
    "         '7': ['8'],\n",
    "         '9': ['8'],}\n",
    "res = graph_dfs(graph2, '0')\n",
    "print(\"->\".join(res))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 广度优先搜索法（BFS）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A->B->C->D->E->F->G\n"
     ]
    }
   ],
   "source": [
    "def graph_bfs(adjacency_list, start_point):\n",
    "    visited = [start_point] # 保存已经访问过的顶点\n",
    "    queue = []              # 用队列结构来记录访问历史\n",
    "    queue.append(start_point)\n",
    "    while len(queue) > 0:   # 当队列为空，说明全部顶点已经遍历完成\n",
    "        current_point = queue.pop(0)  # 获取访问历史的队头为当前顶点\n",
    "        for next_point in adjacency_list.get(current_point, []):\n",
    "            # 逐一访问当前顶点的所有关联点\n",
    "            if next_point not in visited:  \n",
    "                visited.append(next_point)\n",
    "                queue.append(next_point)   # 在队尾添加顶点作为访问记录\n",
    "    return visited\n",
    "#------------测试--------------------\n",
    "res = graph_bfs(graph, 'A')\n",
    "print(\"->\".join(res))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战1：一笔画小游戏"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class solution_dfs():\n",
    "    \"\"\"用深度优先遍历方法来找一笔画路径\"\"\"\n",
    "    def __init__(self, arr):\n",
    "        self.map_array = arr        # 游戏初始化地图\n",
    "        self.map_height = len(arr)  # 网格高度\n",
    "        self.map_width = len(arr[0])# 网格宽度\n",
    "        self.stack = []             # 一笔画的路径\n",
    "\n",
    "    #寻找开始的点\n",
    "    def find_start_point(self):\n",
    "        for x in range(len(self.map_array)):\n",
    "            for y in range(len(self.map_array[x])):\n",
    "                if self.map_array[x][y]==1:  # 选择网格值为1的坐标\n",
    "                    return [x,y]\n",
    "    #判断是否结束\n",
    "    def is_finished(self):\n",
    "        for i in self.map_array:\n",
    "            if 0 in i:  # 若还存在值为0的网格，证明没有结束\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    #获取下一步的位置\n",
    "    def get_next_point(self, current_x, current_y):\n",
    "        #顺序是上，右，下，左边\n",
    "        next_points_list = []\n",
    "        if current_x >= 1 and self.map_array[current_x-1][current_y] == 0:\n",
    "            next_points_list.append([current_x-1, current_y])\n",
    "        if current_y < self.map_width-1 and self.map_array[current_x][current_y+1] == 0:\n",
    "            next_points_list.append([current_x, current_y+1])\n",
    "        if current_x < self.map_height-1  and self.map_array[current_x+1][current_y] == 0:\n",
    "            next_points_list.append([current_x + 1, current_y])\n",
    "        if current_y >= 1 and self.map_array[current_x][current_y-1] == 0:\n",
    "            next_points_list.append([current_x, current_y - 1])\n",
    "        return next_points_list\n",
    "    \n",
    "    #深度优先递归寻找路径\n",
    "    def step_to_next(self):\n",
    "        if self.is_finished(): # 是否已经找到答案\n",
    "            return True\n",
    "        next_steps = self.get_next_point(self.stack[-1][0], self.stack[-1][1]) #根据栈顶的网格获取下一个网格位置\n",
    "        for setp in next_steps:\n",
    "            self.map_array[setp[0]][setp[1]] = 1 # 网格被访问后值变成1\n",
    "            self.stack.append(setp)              # 当前网格入栈\n",
    "            if self.step_to_next(): # 递归寻找未访问网格\n",
    "                return True\n",
    "            else:\n",
    "                self.stack.pop()   # 此路径不满足条件，把当前网格出栈，退回上一个网格\n",
    "                self.map_array[setp[0]][setp[1]]=0 # 当前网格变回未访问，值为0\n",
    "        return False\n",
    "\n",
    "    def start_game(self): # 启动游戏\n",
    "        self.stack.append(self.find_start_point())# 把游戏给出的开始网格作为开始点\n",
    "        if self.step_to_next(): # 开始遍历所有网格\n",
    "            print(self.stack)\n",
    "            return self.stack\n",
    "        else:\n",
    "            print('没有找到解决办法')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "map_array = [\n",
    "    [0,0,-1,0],\n",
    "    [0,0,0,0], \n",
    "    [0,1,0,0], # 起始位置那就是默认是已经访问了 \n",
    "    [0,0,0,0]\n",
    "]\n",
    "print(\"不可访问的格子(0,2)：\", map_array[0][2])\n",
    "s = solution_dfs(map_array)\n",
    "res = s.start_game()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt # 引入matplotlib-2D画图库\n",
    "def find_one_path_plot(self, width, height):\n",
    "    \"\"\"展示寻找一条路径\"\"\"\n",
    "    fig, ax1 = plt.subplots()  # 首先创建画布\n",
    "    # ax1主刻度配置\n",
    "    ax1.set_xticks(range(width))\n",
    "    ax1.set_yticks(range(height))\n",
    "    # ax1次刻度配置\n",
    "    ax1.set_xticks(np.arange(width) + 0.5, minor=True)\n",
    "    ax1.set_yticks(np.arange(height) + 0.5, minor=True)\n",
    "    # 添加网格\n",
    "    ax1.xaxis.grid(True, which='minor', lw=5, color='yellow')\n",
    "    ax1.yaxis.grid(True, which='minor', lw=5, color='yellow')\n",
    "    plt.title('one step draw')\n",
    "    x = [p[0] for p in res]\n",
    "    y = [p[1] for p in res]\n",
    "    ax1.plot(x, y, '-o',lw=18)\n",
    "    plt.show()\n",
    "# 把结果画出来\n",
    "find_one_path_plot(res, s.map_width, s.map_height)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
